SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Approximation algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Approximation algorithm</span></span>

</h1>

</header>

<p>In <a href="Computer_science" title="Computer science">computer science</a> and <a href="Operations_research" title="Operations research">operations research</a>, <b>approximation algorithms</b> are <a href="Time_complexity#Polynomial_time" title="Time complexity">efficient</a> <a href="Algorithm" title="Algorithm">algorithms</a> that find <a href="Approximation" title="Approximation">approximate</a> solutions to <a href="Optimization_problem" title="Optimization problem">optimization problems</a> (in particular <a href="NP-hardness" title="NP-hardness">NP-hard</a> problems) with provable guarantees on the distance of the returned solution to the optimal one.<sup id="cite_ref-Bernard._2011_1-0" class="reference"><a href="#cite_note-Bernard._2011-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Approximation algorithms naturally arise in the field of <a href="Theoretical_computer_science" title="Theoretical computer science">theoretical computer science</a> as a consequence of the widely believed <a href="P_versus_NP_problem" title="P versus NP problem">P ≠ NP</a> conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in <a href="Time_complexity" title="Time complexity">polynomial time</a>. The field of approximation algorithms, therefore, tries to understand how closely it is possible to approximate optimal solutions to such problems in polynomial time. In an overwhelming majority of the cases, the guarantee of such algorithms is a multiplicative one expressed as an approximation ratio or approximation factor i.e., the optimal solution is always guaranteed to be within a (predetermined) multiplicative factor of the returned solution. However, there are also many approximation algorithms that provide an additive guarantee on the quality of the returned solution. A notable example of an approximation algorithm that provides <i>both</i> is the classic approximation algorithm of <a href="Jan_Karel_Lenstra" title="Jan Karel Lenstra">Lenstra</a>, <a href="David_Shmoys" title="David Shmoys">Shmoys</a> and <a href="%C3%89va_Tardos" title="Éva Tardos">Tardos</a><sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> for <a href="Scheduling_(computing)" title="Scheduling (computing)">scheduling</a> on unrelated parallel machines.

</p><p>The design and <a href="Mathematical_analysis" title="Mathematical analysis">analysis</a> of approximation algorithms crucially involves a <a href="Mathematical_proof" title="Mathematical proof">mathematical proof</a> certifying the quality of the returned solutions in the worst case.<sup id="cite_ref-Bernard._2011_1-1" class="reference"><a href="#cite_note-Bernard._2011-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> This distinguishes them from <a href="Heuristic_(computer_science)" title="Heuristic (computer science)">heuristics</a> such as <a href="Simulated_annealing" title="Simulated annealing">annealing</a> or <a href="Genetic_algorithm" title="Genetic algorithm">genetic algorithms</a>, which find reasonably good solutions on some inputs, but provide no clear indication at the outset on when they may succeed or fail.

</p><p>There is widespread interest in <a href="Theoretical_computer_science" title="Theoretical computer science">theoretical computer science</a> to better understand the limits to which we can approximate certain famous optimization problems. For example, one of the long-standing open questions in computer science is to determine whether there is an algorithm that outperforms the 2-approximation for the Steiner Forest problem by Agrawal et al.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> The desire to understand hard optimization problems from the perspective of approximability is motivated by the discovery of surprising mathematical connections and broadly applicable techniques to design algorithms for hard optimization problems. One well-known example of the former is the <a href="Semidefinite_programming#Example_3_(Goemans–Williamson_max_cut_approximation_algorithm)" title="Semidefinite programming">Goemans–Williamson algorithm</a> for <a href="Maximum_cut" title="Maximum cut">maximum cut</a>, which solves a graph theoretic problem using high dimensional geometry.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Introduction">Introduction</h2></div>

<p>A simple example of an approximation algorithm is one for the <a href="Vertex_cover" title="Vertex cover">minimum vertex cover</a> problem, where the goal is to choose the smallest set of vertices such that every edge in the input graph contains at least one chosen vertex. One way to find a <a href="Vertex_cover" title="Vertex cover">vertex cover</a> is to repeat the following process: find an uncovered edge, add both its endpoints to the cover, and remove all edges incident to either vertex from the graph. As any vertex cover of the input graph must use a distinct vertex to cover each edge that was considered in the process (since it forms a <a href="Matching_(graph_theory)" title="Matching (graph theory)">matching</a>), the vertex cover produced, therefore, is at most twice as large as the optimal one. In other words, this is a <a href="Constant-factor_approximation_algorithm" class="mw-redirect" title="Constant-factor approximation algorithm">constant-factor approximation algorithm</a> with an approximation factor of 2. Under the recent <a href="Unique_games_conjecture" title="Unique games conjecture">unique games conjecture</a>, this factor is even the best possible one.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>

</p><p>NP-hard problems vary greatly in their approximability; some, such as the <a href="Knapsack_problem" title="Knapsack problem">knapsack problem</a>, can be approximated within a multiplicative factor <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1+\epsilon }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1+\epsilon }</annotation>

</semantics>

</math></span><img src="./d0a9509a716b94626789c0045ba24d98dc3a02d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:4.947ex; height:2.343ex;" alt="{\displaystyle 1+\epsilon }" loading="lazy"></span>, for any fixed <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon >0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon >0}</annotation>

</semantics>

</math></span><img src="./568095ad3924314374a5ab68fae17343661f2a71.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.205ex; height:2.176ex;" alt="{\displaystyle \epsilon >0}" loading="lazy"></span>, and therefore produce solutions arbitrarily close to the optimum (such a family of approximation algorithms is called a <a href="Polynomial-time_approximation_scheme" title="Polynomial-time approximation scheme">polynomial-time approximation scheme</a> or PTAS). Others are impossible to approximate within any constant, or even polynomial, factor unless <a href="P_%3D_NP" class="mw-redirect" title="P = NP">P = NP</a>, as in the case of the <a href="Clique_problem" title="Clique problem">maximum clique problem</a>. Therefore, an important benefit of studying approximation algorithms is a fine-grained classification of the difficulty of various NP-hard problems beyond the one afforded by the <a href="NP-completeness" title="NP-completeness">theory of NP-completeness</a>. In other words, although NP-complete problems may be equivalent (under polynomial-time reductions) to each other from the perspective of exact solutions, the corresponding optimization problems behave very differently from the perspective of approximate solutions.

</p>

<div class="mw-heading mw-heading2"><h2 id="Algorithm_design_techniques">Algorithm design techniques</h2></div>

<p>By now there are several established techniques to design approximation algorithms. These include the following ones.

</p>

<ol><li><a href="Greedy_algorithm" title="Greedy algorithm">Greedy algorithm</a></li>

<li><a href="Local_search_(optimization)" title="Local search (optimization)">Local search</a></li>

<li>Enumeration and <a href="Dynamic_programming" title="Dynamic programming">dynamic programming</a> (which is also often used for <a href="Parameterized_approximation_algorithm" title="Parameterized approximation algorithm">parameterized approximations</a>)</li>

<li>Solving a <a href="Convex_programming" class="mw-redirect" title="Convex programming">convex programming</a> relaxation to get a fractional solution. Then converting this fractional solution into a feasible solution by some appropriate rounding. The popular relaxations include the following.

<ul><li><a href="Linear_programming" title="Linear programming">Linear programming</a> relaxations</li>

<li><a href="Semidefinite_programming" title="Semidefinite programming">Semidefinite programming</a> relaxations</li></ul></li>

<li>Primal-dual methods</li>

<li>Dual fitting</li>

<li>Embedding the problem in some metric and then solving the problem on the metric. This is also known as metric embedding.</li>

<li>Random sampling and the use of randomness in general in conjunction with the methods above.</li></ol>

<div class="mw-heading mw-heading2"><h2 id="A_posteriori_guarantees">A posteriori guarantees</h2></div>

<p>While approximation algorithms always provide an a priori worst case guarantee (be it additive or multiplicative), in some cases they also provide an a posteriori guarantee that is often much better. This is often the case for algorithms that work by solving a <a href="Convex_programming" class="mw-redirect" title="Convex programming">convex relaxation</a> of the optimization problem on the given input. For example, there is a different approximation algorithm for minimum vertex cover that solves a <a href="Linear_programming_relaxation" title="Linear programming relaxation">linear programming relaxation</a> to find a vertex cover that is at most twice the value of the relaxation. Since the value of the relaxation is never larger than the size of the optimal vertex cover, this yields another 2-approximation algorithm. While this is similar to the a priori guarantee of the previous approximation algorithm, the guarantee of the latter can be much better (indeed when the value of the LP relaxation is far from the size of the optimal vertex cover).

</p>

<div class="mw-heading mw-heading2"><h2 id="Hardness_of_approximation">Hardness of approximation</h2></div>

<p>Approximation algorithms as a research area is closely related to and informed by <a href="Hardness_of_approximation" title="Hardness of approximation">inapproximability theory</a> where the non-existence of efficient algorithms with certain approximation ratios is proved (conditioned on widely believed hypotheses such as the P ≠ NP conjecture) by means of <a href="Reduction_(complexity)" title="Reduction (complexity)">reductions</a>. In the case of the metric traveling salesman problem, the best known inapproximability result rules out algorithms with an approximation ratio less than 123/122 ≈ 1.008196 unless P = NP, Karpinski, Lampis, Schmied.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> Coupled with the knowledge of the existence of Christofides' 1.5 approximation algorithm, this tells us that the threshold of approximability for metric traveling salesman (if it exists) is somewhere between 123/122 and 1.5.

</p><p>While inapproximability results have been proved since the 1970s, such results were obtained by ad hoc means and no systematic understanding was available at the time. It is only since the 1990 result of Feige, Goldwasser, Lovász, Safra and Szegedy on the inapproximability of <a href="Independent_set_(graph_theory)" title="Independent set (graph theory)">Independent Set</a><sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> and the famous <a href="PCP_theorem" title="PCP theorem">PCP theorem</a>,<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> that modern tools for proving inapproximability results were uncovered. The PCP theorem, for example, shows that <a href="David_S._Johnson" title="David S. Johnson">Johnson's</a> 1974 approximation algorithms for <a href="Maximum_satisfiability_problem" title="Maximum satisfiability problem">Max SAT</a>, <a href="Set_cover_problem" title="Set cover problem">set cover</a>, <a href="Independent_set_(graph_theory)" title="Independent set (graph theory)">independent set</a> and <a href="Graph_coloring" title="Graph coloring">coloring</a> all achieve the optimal approximation ratio, assuming P ≠ NP.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Practicality">Practicality</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">See also: <a href="Galactic_algorithm" title="Galactic algorithm">Galactic algorithm</a></div>

<p>Not all approximation algorithms are suitable for direct practical applications. Some involve solving non-trivial <a href="Linear_programming_relaxation" title="Linear programming relaxation">linear programming</a>/<a href="Semidefinite_programming" title="Semidefinite programming">semidefinite</a> relaxations (which may themselves invoke the <a href="Ellipsoid_method" title="Ellipsoid method">ellipsoid algorithm</a>), complex data structures, or sophisticated algorithmic techniques, leading to difficult implementation issues or improved running time performance (over exact algorithms) only on impractically large inputs. Implementation and running time issues aside, the guarantees provided by approximation algorithms may themselves not be strong enough to justify their consideration in practice. Despite their inability to be used "out of the box" in practical applications, the ideas and insights behind the design of such algorithms can often be incorporated in other ways in practical algorithms. In this way, the study of even very expensive algorithms is not a completely theoretical pursuit as they can yield valuable insights.

</p><p>In other cases, even if the initial results are of purely theoretical interest, over time, with an improved understanding, the algorithms may be refined to become more practical. One such example is the initial PTAS for <a href="Euclidean_traveling_salesman_problem" class="mw-redirect" title="Euclidean traveling salesman problem">Euclidean TSP</a> by <a href="Sanjeev_Arora" title="Sanjeev Arora">Sanjeev Arora</a> (and independently by <a href="Joseph_S._B._Mitchell" title="Joseph S. B. Mitchell">Joseph Mitchell</a>) which had a prohibitive running time of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{O(1/\epsilon )}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{O(1/\epsilon )}}</annotation>

</semantics>

</math></span><img src="./a3ceb3173fa796750158d3566b743d43b0f30f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.472ex; height:2.843ex;" alt="{\displaystyle n^{O(1/\epsilon )}}" loading="lazy"></span> for a <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1+\epsilon }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1+\epsilon }</annotation>

</semantics>

</math></span><img src="./d0a9509a716b94626789c0045ba24d98dc3a02d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:4.947ex; height:2.343ex;" alt="{\displaystyle 1+\epsilon }" loading="lazy"></span> approximation.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> Yet, within a year these ideas were incorporated into a near-linear time <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation>

</semantics>

</math></span><img src="./9d2320768fb54880ca4356e61f60eb02a3f9d9f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}" loading="lazy"></span> algorithm for any constant <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon >0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon >0}</annotation>

</semantics>

</math></span><img src="./568095ad3924314374a5ab68fae17343661f2a71.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.205ex; height:2.176ex;" alt="{\displaystyle \epsilon >0}" loading="lazy"></span>.<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Structure_of_approximation_algorithms">Structure of approximation algorithms</h2></div>

<p>Given an optimization problem:

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Pi :I\times S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pi :I\times S}</annotation>

</semantics>

</math></span><img src="./005f35a11480f9e64d83e227e1dee30c819a08e9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.192ex; height:2.176ex;" alt="{\displaystyle \Pi :I\times S}" loading="lazy"></span>

</p><p>where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Pi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pi }</annotation>

</semantics>

</math></span><img src="./eed3e3db6cc2028a183af948212ed2551d25c954.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle \Pi }" loading="lazy"></span> is an approximation problem, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle I}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I}</annotation>

</semantics>

</math></span><img src="./535ea7fc4134a31cbe2251d9d3511374bc41be9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.172ex; height:2.176ex;" alt="{\displaystyle I}" loading="lazy"></span> the set of inputs and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span> the set of solutions, we can define the cost function:

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c:S\rightarrow \mathbb {R} ^{+}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c:S\rightarrow \mathbb {R} ^{+}}</annotation>

</semantics>

</math></span><img src="./61f7e26b37f062480aee251e2eacca43b1082851.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:11.246ex; height:2.509ex;" alt="{\displaystyle c:S\rightarrow \mathbb {R} ^{+}}" loading="lazy"></span>

</p><p>and the set of feasible solutions:

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \forall i\in I,S(i)={s\in S:i\Pi _{s}}}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \forall i\in I,S(i)={s\in S:i\Pi _{s}}}</annotation>

</semantics>

</math></span><img src="./5e0791d690cf1ab95d3d86a504e0c8b721e2eb37.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.267ex; height:2.843ex;" alt="{\displaystyle \forall i\in I,S(i)={s\in S:i\Pi _{s}}}" loading="lazy"></span>

</p><p>finding the best solution <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s^{*}}</annotation>

</semantics>

</math></span><img src="./c0dd30e91ecca56ddf4ee71bf82b506b3249a5f6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.145ex; height:2.343ex;" alt="{\displaystyle s^{*}}" loading="lazy"></span> for a maximization or a minimization problem:

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s^{*}\in S(i)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s^{*}\in S(i)}</annotation>

</semantics>

</math></span><img src="./0d40f600a2dd763e32e26b742b9d41046f2a41c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.096ex; height:2.843ex;" alt="{\displaystyle s^{*}\in S(i)}" loading="lazy"></span>, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c(s^{*})=min/max\ c(S(i))}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c(s^{*})=min/max\ c(S(i))}</annotation>

</semantics>

</math></span><img src="./e129e6829e7d4b5c8ec8e3d64dca35e1a00aff29.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.567ex; height:2.843ex;" alt="{\displaystyle c(s^{*})=min/max\ c(S(i))}" loading="lazy"></span>

</p><p>Given a feasible solution <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s\in S(i)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s\in S(i)}</annotation>

</semantics>

</math></span><img src="./a5562e3c5bbde35b591590a41b55c048950868ad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.042ex; height:2.843ex;" alt="{\displaystyle s\in S(i)}" loading="lazy"></span>, with <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s\neq s^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s\neq s^{*}}</annotation>

</semantics>

</math></span><img src="./a78ce7fce7c089c394b9ff06d22690003c940a4b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.334ex; height:2.843ex;" alt="{\displaystyle s\neq s^{*}}" loading="lazy"></span>, we would want a guarantee of the quality of the solution, which is a performance to be guaranteed (approximation factor).

</p><p>Specifically, having <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A_{\Pi }(i)\in S_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A_{\Pi }(i)\in S_{i}}</annotation>

</semantics>

</math></span><img src="./c50a9ae2a30aefd674b51cacdd760b4563cf64a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.885ex; height:2.843ex;" alt="{\displaystyle A_{\Pi }(i)\in S_{i}}" loading="lazy"></span>, the algorithm has an <b>approximation factor</b> (or <b>approximation ratio</b>) of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho (n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho (n)}</annotation>

</semantics>

</math></span><img src="./9ae6340a96b8959ed108cdd382db66172a2ba33a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.406ex; height:2.843ex;" alt="{\displaystyle \rho (n)}" loading="lazy"></span> if <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \forall i\in I\ s.t.|i|=n}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \forall i\in I\ s.t.|i|=n}</annotation>

</semantics>

</math></span><img src="./8b2b0d5411059f1e6faddb34fd29322661f95e2f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.275ex; height:2.843ex;" alt="{\displaystyle \forall i\in I\ s.t.|i|=n}" loading="lazy"></span>, we have:

</p>

<ul><li>for a <i>minimization</i> problem: <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {c(A_{\Pi }(i))}{c(s^{*}(i))}}\leq \rho (n)}">

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {c(A_{\Pi }(i))}{c(s^{*}(i))}}\leq \rho (n)}</annotation>

</semantics>

</math></span><img src="./16f48646a5ec53bf9bf3e77fe81fbb65bc8b9ff5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:16.976ex; height:6.509ex;" alt="{\displaystyle {\frac {c(A_{\Pi }(i))}{c(s^{*}(i))}}\leq \rho (n)}" loading="lazy"></span>, which in turn means the solution taken by the algorithm divided by the optimal solution achieves a ratio of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho (n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho (n)}</annotation>

</semantics>

</math></span><img src="./9ae6340a96b8959ed108cdd382db66172a2ba33a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.406ex; height:2.843ex;" alt="{\displaystyle \rho (n)}" loading="lazy"></span>;</li>

<li>for a <i>maximization</i> problem: <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {c(s^{*}(i))}{c(A_{\Pi }(i))}}\leq \rho (n)}">

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {c(s^{*}(i))}{c(A_{\Pi }(i))}}\leq \rho (n)}</annotation>

</semantics>

</math></span><img src="./17197746c59be01dde46ec8ce51193c4d93c3ea4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:16.976ex; height:6.509ex;" alt="{\displaystyle {\frac {c(s^{*}(i))}{c(A_{\Pi }(i))}}\leq \rho (n)}" loading="lazy"></span>, which in turn means the optimal solution divided by the solution taken by the algorithm achieves a ratio of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho (n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho (n)}</annotation>

</semantics>

</math></span><img src="./9ae6340a96b8959ed108cdd382db66172a2ba33a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.406ex; height:2.843ex;" alt="{\displaystyle \rho (n)}" loading="lazy"></span>;</li></ul>

<p>The approximation can be proven <i>tight</i> (<i>tight approximation</i>) by demonstrating that there exist instances where the algorithm performs at the approximation limit, indicating the tightness of the bound. In this case, it's enough to construct an input instance designed to force the algorithm into a worst-case scenario.

</p>

<div class="mw-heading mw-heading2"><h2 id="Performance_guarantees">Performance guarantees</h2></div>

<p>For some approximation algorithms it is possible to prove certain properties about the approximation of the optimum result. For example, a <b><i>ρ</i>-approximation algorithm</b> <i>A</i> is defined to be an algorithm for which it has been proven that the value/cost, <i>f</i>(<i>x</i>), of the approximate solution <i>A</i>(<i>x</i>) to an instance <i>x</i> will not be more (or less, depending on the situation) than a factor <i>ρ</i> times the value, OPT, of an optimum solution.

</p>

<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{cases}\mathrm {OPT} \leq f(x)\leq \rho \mathrm {OPT} ,\qquad {\mbox{if }}\rho >1;\\\rho \mathrm {OPT} \leq f(x)\leq \mathrm {OPT} ,\qquad {\mbox{if }}\rho <1.\end{cases}}}">

<mrow>

<mtr>

<mtd>

</mrow>

</mrow>

</mstyle>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</mstyle>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{cases}\mathrm {OPT} \leq f(x)\leq \rho \mathrm {OPT} ,\qquad {\mbox{if }}\rho >1;\\\rho \mathrm {OPT} \leq f(x)\leq \mathrm {OPT} ,\qquad {\mbox{if }}\rho <1.\end{cases}}}</annotation>

</semantics>

</math></span><img src="./d994a747b373509565531a3a90f73c8297824427.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:38.177ex; height:6.176ex;" alt="{\displaystyle {\begin{cases}\mathrm {OPT} \leq f(x)\leq \rho \mathrm {OPT} ,\qquad {\mbox{if }}\rho >1;\\\rho \mathrm {OPT} \leq f(x)\leq \mathrm {OPT} ,\qquad {\mbox{if }}\rho <1.\end{cases}}}" loading="lazy"></span></dd></dl>

<p>The factor <i>ρ</i> is called the <i>relative performance guarantee</i>. An approximation algorithm has an <i>absolute performance guarantee</i> or <i>bounded error</i> <i>c</i>, if it has been proven for every instance <i>x</i> that

</p>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\mathrm {OPT} -c)\leq f(x)\leq (\mathrm {OPT} +c).}</annotation>

</semantics>

</math></span><img src="./1e9d1c2884e673516af7e506f4710d375832fb33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:32.713ex; height:2.843ex;" alt="{\displaystyle (\mathrm {OPT} -c)\leq f(x)\leq (\mathrm {OPT} +c).}" loading="lazy"></span></dd></dl>

<p>Similarly, the <i>performance guarantee</i>, <i>R</i>(<i>x,y</i>), of a solution <i>y</i> to an instance <i>x</i> is defined as

</p>

<mrow>

<mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R(x,y)=\max \left({\frac {OPT}{f(y)}},{\frac {f(y)}{OPT}}\right),}</annotation>

</semantics>

</math></span><img src="./df47f6cb9d044eac8550fe4465aa4189e734a46b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:32.375ex; height:6.509ex;" alt="{\displaystyle R(x,y)=\max \left({\frac {OPT}{f(y)}},{\frac {f(y)}{OPT}}\right),}" loading="lazy"></span></dd></dl>

<p>where <i>f</i>(<i>y</i>) is the value/cost of the solution <i>y</i> for the instance <i>x</i>. Clearly, the performance guarantee is greater than or equal to 1 and equal to 1 if and only if <i>y</i> is an optimal solution. If an algorithm <i>A</i> guarantees to return solutions with a performance guarantee of at most <i>r</i>(<i>n</i>), then <i>A</i> is said to be an <i>r</i>(<i>n</i>)-approximation algorithm and has an <i>approximation ratio</i> of <i>r</i>(<i>n</i>). Likewise, a problem with an <i>r</i>(<i>n</i>)-approximation algorithm is said to be r<i>(</i>n<i>)</i>-<i>approximable</i> or have an approximation ratio of <i>r</i>(<i>n</i>).<sup id="cite_ref-ausiello99complexity_12-0" class="reference"><a href="#cite_note-ausiello99complexity-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-kann92onthe_13-0" class="reference"><a href="#cite_note-kann92onthe-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup>

</p><p>For minimization problems, the two different guarantees provide the same result and that for maximization problems, a relative performance guarantee of ρ is equivalent to a performance guarantee of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r=\rho ^{-1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r=\rho ^{-1}}</annotation>

</semantics>

</math></span><img src="./398f47c8b7c4ec6c6336b23555d63fb50aaa1832.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.682ex; height:3.176ex;" alt="{\displaystyle r=\rho ^{-1}}" loading="lazy"></span>. In the literature, both definitions are common but it is clear which definition is used since, for maximization problems, as ρ ≤ 1 while r ≥ 1.

</p><p>The <i>absolute performance guarantee</i> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {P} _{A}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {P} _{A}}</annotation>

</semantics>

</math></span><img src="./29afbd79c33a5d1ec8780205292049d80a79d3e5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.048ex; height:2.509ex;" alt="{\displaystyle \mathrm {P} _{A}}" loading="lazy"></span> of some approximation algorithm <i>A</i>, where <i>x</i> refers to an instance of a problem, and where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{A}(x)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R_{A}(x)}</annotation>

</semantics>

</math></span><img src="./4e937c44f7baf168bfce95a7ffaa38f5be525d47.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.368ex; height:2.843ex;" alt="{\displaystyle R_{A}(x)}" loading="lazy"></span> is the performance guarantee of <i>A</i> on <i>x</i> (i.e. ρ for problem instance <i>x</i>) is:

</p>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {P} _{A}=\inf\{r\geq 1\mid R_{A}(x)\leq r,\forall x\}.}</annotation>

</semantics>

</math></span><img src="./76ae7e8b631ed0ead74532ac84f37e09d85efc1a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.187ex; height:2.843ex;" alt="{\displaystyle \mathrm {P} _{A}=\inf\{r\geq 1\mid R_{A}(x)\leq r,\forall x\}.}" loading="lazy"></span></dd></dl>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {P} _{A}}</annotation>

</semantics>

</math></span><img src="./29afbd79c33a5d1ec8780205292049d80a79d3e5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.048ex; height:2.509ex;" alt="{\displaystyle \mathrm {P} _{A}}" loading="lazy"></span> is the largest bound on the approximation ratio, <i>r</i>, that one sees over all possible instances of the problem. Likewise, the <i>asymptotic performance ratio</i> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{A}^{\infty }}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R_{A}^{\infty }}</annotation>

</semantics>

</math></span><img src="./b90ef343c32c5c68c9e078d0402864306f40be14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.639ex; height:2.843ex;" alt="{\displaystyle R_{A}^{\infty }}" loading="lazy"></span> is:

</p>

</mrow>

</mrow>

</msubsup>

<msup>

</mrow>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R_{A}^{\infty }=\inf\{r\geq 1\mid \exists n\in \mathbb {Z} ^{+},R_{A}(x)\leq r,\forall x,|x|\geq n\}.}</annotation>

</semantics>

</math></span><img src="./4ba11045c201534bf3ca6af3de5479f4b2f4accd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:51.552ex; height:3.176ex;" alt="{\displaystyle R_{A}^{\infty }=\inf\{r\geq 1\mid \exists n\in \mathbb {Z} ^{+},R_{A}(x)\leq r,\forall x,|x|\geq n\}.}" loading="lazy"></span></dd></dl>

<p>That is to say that it is the same as the <i>absolute performance ratio</i>, with a lower bound <i>n</i> on the size of problem instances. These two types of ratios are used because there exist algorithms where the difference between these two is significant.

</p>

<caption>Performance guarantees

</caption>

<th><i>r</i>-approx<sup id="cite_ref-ausiello99complexity_12-1" class="reference"><a href="#cite_note-ausiello99complexity-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-kann92onthe_13-1" class="reference"><a href="#cite_note-kann92onthe-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup></th>

<th><i>ρ</i>-approx</th>

<th>rel. error<sup id="cite_ref-kann92onthe_13-2" class="reference"><a href="#cite_note-kann92onthe-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup></th>

<th>rel. error<sup id="cite_ref-ausiello99complexity_12-2" class="reference"><a href="#cite_note-ausiello99complexity-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup></th>

<th>norm. rel. error<sup id="cite_ref-ausiello99complexity_12-3" class="reference"><a href="#cite_note-ausiello99complexity-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-kann92onthe_13-3" class="reference"><a href="#cite_note-kann92onthe-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup></th>

<th>abs. error<sup id="cite_ref-ausiello99complexity_12-4" class="reference"><a href="#cite_note-ausiello99complexity-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-kann92onthe_13-4" class="reference"><a href="#cite_note-kann92onthe-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup>

</th></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)\geq }</annotation>

</semantics>

</math></span><img src="./5c1e4f0ff2b8b646c481ba7fc3ddef6c68f768fb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.871ex; height:2.843ex;" alt="{\displaystyle f(x)\geq }" loading="lazy"></span>

</th>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r^{-1}\mathrm {OPT} }</annotation>

</semantics>

</math></span><img src="./de8b7b90513b322fd6a89cf06ba8094d6788f7e5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.45ex; height:2.676ex;" alt="{\displaystyle r^{-1}\mathrm {OPT} }" loading="lazy"></span></td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho \mathrm {OPT} }</annotation>

</semantics>

</math></span><img src="./710eb2beaa790ad445c50199d983d0ff9dec6d0b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.271ex; height:2.676ex;" alt="{\displaystyle \rho \mathrm {OPT} }" loading="lazy"></span></td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (1-c)\mathrm {OPT} }</annotation>

</semantics>

</math></span><img src="./3844fbfb9697a432950a14d4d078f6d87f032ebc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.888ex; height:2.843ex;" alt="{\displaystyle (1-c)\mathrm {OPT} }" loading="lazy"></span></td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (1-c)\mathrm {OPT} }</annotation>

</semantics>

</math></span><img src="./3844fbfb9697a432950a14d4d078f6d87f032ebc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.888ex; height:2.843ex;" alt="{\displaystyle (1-c)\mathrm {OPT} }" loading="lazy"></span></td>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (1-c)\mathrm {OPT} +c\mathrm {WORST} }</annotation>

</semantics>

</math></span><img src="./c2fabb5c077ccda3b338a7b5af4aea953a47cecb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.613ex; height:2.843ex;" alt="{\displaystyle (1-c)\mathrm {OPT} +c\mathrm {WORST} }" loading="lazy"></span></td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {OPT} -c}</annotation>

</semantics>

</math></span><img src="./2e0683282c02a35a16cd39887934648c1f18cf3a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:8.916ex; height:2.343ex;" alt="{\displaystyle \mathrm {OPT} -c}" loading="lazy"></span>

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)\leq }</annotation>

</semantics>

</math></span><img src="./74dbd0a04719363164b4120843543898b8dc6457.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.871ex; height:2.843ex;" alt="{\displaystyle f(x)\leq }" loading="lazy"></span>

</th>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r\mathrm {OPT} }</annotation>

</semantics>

</math></span><img src="./5e0497c9c001cceb1e018cc2f0667e0fab235d27.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.118ex; height:2.176ex;" alt="{\displaystyle r\mathrm {OPT} }" loading="lazy"></span></td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho \mathrm {OPT} }</annotation>

</semantics>

</math></span><img src="./710eb2beaa790ad445c50199d983d0ff9dec6d0b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.271ex; height:2.676ex;" alt="{\displaystyle \rho \mathrm {OPT} }" loading="lazy"></span></td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (1+c)\mathrm {OPT} }</annotation>

</semantics>

</math></span><img src="./df1645cfca65b1c3484bfdc287cbf19c44516d75.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.888ex; height:2.843ex;" alt="{\displaystyle (1+c)\mathrm {OPT} }" loading="lazy"></span></td>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (1-c)^{-1}\mathrm {OPT} }</annotation>

</semantics>

</math></span><img src="./d125e35568444feb5eb57aba061a38004c102132.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.221ex; height:3.176ex;" alt="{\displaystyle (1-c)^{-1}\mathrm {OPT} }" loading="lazy"></span></td>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (1-c)^{-1}\mathrm {OPT} +c\mathrm {WORST} }</annotation>

</semantics>

</math></span><img src="./296b5fb138d595b38a0feecc8ebdaf0fdd0c5487.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.946ex; height:3.176ex;" alt="{\displaystyle (1-c)^{-1}\mathrm {OPT} +c\mathrm {WORST} }" loading="lazy"></span></td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {OPT} +c}</annotation>

</semantics>

</math></span><img src="./884aff39a96fad23c42ed8347bf494d52ba9f7e7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:8.916ex; height:2.343ex;" alt="{\displaystyle \mathrm {OPT} +c}" loading="lazy"></span>

</td></tr>

</tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Epsilon_terms">Epsilon terms</h2></div>

<p>In the literature, an approximation ratio for a maximization (minimization) problem of <i>c</i> - ϵ (min: <i>c</i> + ϵ) means that the algorithm has an approximation ratio of <i>c</i> ∓ ϵ for arbitrary ϵ > 0 but that the ratio has not (or cannot) be shown for ϵ = 0. An example of this is the optimal inapproximability — inexistence of approximation — ratio of 7 / 8 + ϵ for satisfiable <a href="MAX-3SAT" title="MAX-3SAT">MAX-3SAT</a> instances due to <a href="Johan_H%C3%A5stad" title="Johan Håstad">Johan Håstad</a>.<sup id="cite_ref-hastad99someoptimal_14-0" class="reference"><a href="#cite_note-hastad99someoptimal-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> As mentioned previously, when <i>c</i> = 1, the problem is said to have a <a href="Polynomial-time_approximation_scheme" title="Polynomial-time approximation scheme">polynomial-time approximation scheme</a>.

</p><p>An ϵ-term may appear when an approximation algorithm introduces a multiplicative error and a constant error while the minimum optimum of instances of size <i>n</i> goes to infinity as <i>n</i> does. In this case, the approximation ratio is <i>c</i> ∓ <i>k</i> / OPT = <i>c</i> ∓ o(1) for some constants <i>c</i> and <i>k</i>. Given arbitrary ϵ > 0, one can choose a large enough <i>N</i> such that the term <i>k</i> / OPT < ϵ for every <i>n ≥ N</i>. For every fixed ϵ, instances of size <i>n < N</i> can be solved by brute force, thereby showing an approximation ratio — existence of approximation algorithms with a guarantee — of <i>c</i> ∓ ϵ for every ϵ > 0.

</p>

<ul><li><a href="Domination_analysis" title="Domination analysis">Domination analysis</a> considers guarantees in terms of the rank of the computed solution.</li>

<li><a href="Polynomial-time_approximation_scheme" title="Polynomial-time approximation scheme">PTAS</a> - a type of approximation algorithm that takes the approximation ratio as a parameter</li>

<li><a href="Parameterized_approximation_algorithm" title="Parameterized approximation algorithm">Parameterized approximation algorithm</a> - a type of approximation algorithm that runs in <a href="Fixed-parameter_algorithm" class="mw-redirect" title="Fixed-parameter algorithm">FPT</a> time</li>

<li><a href="APX" title="APX">APX</a> is the class of problems with some constant-factor approximation algorithm</li>

<li><a href="Approximation-preserving_reduction" title="Approximation-preserving reduction">Approximation-preserving reduction</a></li>

<li><a href="Exact_algorithm" title="Exact algorithm">Exact algorithm</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Citations">Citations</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFBernard.2011" class="citation book cs1">Bernard., Shmoys, David (2011). <a rel="nofollow" class="external text" href="http://www.designofapproxalgs.com/"><i>The design of approximation algorithms</i></a>. Cambridge University Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780521195270</bdi>. <a href="OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/671709856">671709856</a>.</cite><span class="cs1-maint citation-comment"><code class="cs1-code">{{cite book}}</code>: CS1 maint: multiple names: authors list (link)</span></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite id="CITEREFLenstraShmoysTardos1990" class="citation journal cs1">Lenstra, Jan Karel; Shmoys, David B.; Tardos, Éva (1990-01-01). "Approximation algorithms for scheduling unrelated parallel machines". <i>Mathematical Programming</i>. <b>46</b> (<span class="nowrap">1–</span>3): <span class="nowrap">259–</span>271. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.115.708">10.1.1.115.708</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01585745">10.1007/BF01585745</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0025-5610">0025-5610</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:206799898">206799898</a>.</cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFAgrawalKleinRavi1991" class="citation book cs1">Agrawal, Ajit; Klein, Philip; Ravi, R. (1991). <a rel="nofollow" class="external text" href="http://portal.acm.org/citation.cfm?doid=103418.103437">"When trees collide"</a>. <i>Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC '91</i>. New Orleans, Louisiana, United States: ACM Press. pp. <span class="nowrap">134–</span>144. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F103418.103437">10.1145/103418.103437</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-89791-397-3</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1245448">1245448</a>.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFGoemansWilliamson1995" class="citation journal cs1">Goemans, Michel X.; Williamson, David P. (November 1995). "Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming". <i>J. ACM</i>. <b>42</b> (6): <span class="nowrap">1115–</span>1145. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.8500">10.1.1.34.8500</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F227683.227684">10.1145/227683.227684</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0004-5411">0004-5411</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:15794408">15794408</a>.</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFKhotRegev2008" class="citation journal cs1">Khot, Subhash; Regev, Oded (2008-05-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jcss.2007.06.019">"Vertex cover might be hard to approximate to within 2−ε"</a>. <i>Journal of Computer and System Sciences</i>. Computational Complexity 2003. <b>74</b> (3): <span class="nowrap">335–</span>349. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jcss.2007.06.019">10.1016/j.jcss.2007.06.019</a></span>.</cite></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite id="CITEREFKarpinskiLampisSchmied2015" class="citation journal cs1">Karpinski, Marek; Lampis, Michael; Schmied, Richard (2015-12-01). "New inapproximability bounds for TSP". <i>Journal of Computer and System Sciences</i>. <b>81</b> (8): <span class="nowrap">1665–</span>1677. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1303.6437">1303.6437</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jcss.2015.06.003">10.1016/j.jcss.2015.06.003</a>.</cite></span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><cite id="CITEREFFeigeGoldwasserLovászSafra1996" class="citation journal cs1">Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario (March 1996). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F226643.226652">"Interactive Proofs and the Hardness of Approximating Cliques"</a>. <i>J. ACM</i>. <b>43</b> (2): <span class="nowrap">268–</span>292. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F226643.226652">10.1145/226643.226652</a></span>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0004-5411">0004-5411</a>.</cite></span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><cite id="CITEREFAroraSafra1998" class="citation journal cs1">Arora, Sanjeev; Safra, Shmuel (January 1998). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F273865.273901">"Probabilistic Checking of Proofs: A New Characterization of NP"</a>. <i>J. ACM</i>. <b>45</b> (1): <span class="nowrap">70–</span>122. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F273865.273901">10.1145/273865.273901</a></span>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0004-5411">0004-5411</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:751563">751563</a>.</cite></span>

</li>

<li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><cite id="CITEREFJohnson1974" class="citation journal cs1">Johnson, David S. (1974-12-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0022-0000%2874%2980044-9">"Approximation algorithms for combinatorial problems"</a>. <i>Journal of Computer and System Sciences</i>. <b>9</b> (3): <span class="nowrap">256–</span>278. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0022-0000%2874%2980044-9">10.1016/S0022-0000(74)80044-9</a></span>.</cite></span>

</li>

<li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><cite id="CITEREFArora1996" class="citation book cs1">Arora, S. (October 1996). "Polynomial time approximation schemes for Euclidean TSP and other geometric problems". <i>Proceedings of 37th Conference on Foundations of Computer Science</i>. pp. <span class="nowrap">2–</span>11. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.3376">10.1.1.32.3376</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSFCS.1996.548458">10.1109/SFCS.1996.548458</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-8186-7594-2</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1499391">1499391</a>.</cite></span>

</li>

<li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><cite id="CITEREFArora1997" class="citation book cs1">Arora, S. (October 1997). "Nearly linear time approximation schemes for Euclidean TSP and other geometric problems". <i>Proceedings 38th Annual Symposium on Foundations of Computer Science</i>. pp. <span class="nowrap">554–</span>563. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSFCS.1997.646145">10.1109/SFCS.1997.646145</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-8186-8197-4</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:10656723">10656723</a>.</cite></span>

</li>

<li id="cite_note-ausiello99complexity-12"><span class="mw-cite-backlink">^ <a href="#cite_ref-ausiello99complexity_12-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-ausiello99complexity_12-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-ausiello99complexity_12-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-ausiello99complexity_12-3"><sup><i><b>d</b></i></sup></a> <a href="#cite_ref-ausiello99complexity_12-4"><sup><i><b>e</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFG._AusielloP._CrescenziG._GambosiV._Kann1999" class="citation book cs1">G. Ausiello; P. Crescenzi; G. Gambosi; V. Kann; A. Marchetti-Spaccamela; M. Protasi (1999). <i>Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties</i>.</cite></span>

</li>

<li id="cite_note-kann92onthe-13"><span class="mw-cite-backlink">^ <a href="#cite_ref-kann92onthe_13-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-kann92onthe_13-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-kann92onthe_13-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-kann92onthe_13-3"><sup><i><b>d</b></i></sup></a> <a href="#cite_ref-kann92onthe_13-4"><sup><i><b>e</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFViggo_Kann1992" class="citation book cs1">Viggo Kann (1992). <a rel="nofollow" class="external text" href="https://www.csc.kth.se/~viggo/papers/phdthesis.pdf"><i>On the Approximability of NP-complete Optimization Problems</i></a> <span class="cs1-format">(PDF)</span>.</cite></span>

</li>

<li id="cite_note-hastad99someoptimal-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-hastad99someoptimal_14-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFJohan_Håstad1999" class="citation journal cs1"><a href="Johan_H%C3%A5stad" title="Johan Håstad">Johan Håstad</a> (1999). <a rel="nofollow" class="external text" href="http://www.nada.kth.se/~johanh/optimalinap.ps">"Some Optimal Inapproximability Results"</a>. <i>Journal of the ACM</i>. <b>48</b> (4): <span class="nowrap">798–</span>859. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.638.2808">10.1.1.638.2808</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F502090.502098">10.1145/502090.502098</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:5120748">5120748</a>.</cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li><cite id="CITEREFVazirani2003" class="citation book cs1"><a href="Vijay_Vazirani" title="Vijay Vazirani">Vazirani, Vijay V.</a> (2003). <i>Approximation Algorithms</i>. Berlin: Springer. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-65367-7</bdi>.</cite></li>

<li><a href="Thomas_H._Cormen" title="Thomas H. Cormen">Thomas H. Cormen</a>, <a href="Charles_E._Leiserson" title="Charles E. Leiserson">Charles E. Leiserson</a>, <a href="Ronald_L._Rivest" class="mw-redirect" title="Ronald L. Rivest">Ronald L. Rivest</a>, and <a href="Clifford_Stein" title="Clifford Stein">Clifford Stein</a>. <i><a href="Introduction_to_Algorithms" title="Introduction to Algorithms">Introduction to Algorithms</a></i>, Second Edition. MIT Press and McGraw-Hill, 2001. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-262-03293-7</bdi>. Chapter 35: Approximation Algorithms, pp. 1022–1056.</li>

<li><a href="Dorit_S._Hochbaum" title="Dorit S. Hochbaum">Dorit S. Hochbaum</a>, ed. <i>Approximation Algorithms for NP-Hard problems</i>, PWS Publishing Company, 1997. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-534-94968-1</bdi>. Chapter 9: Various Notions of Approximations: Good, Better, Best, and More</li>

<li><cite id="CITEREFWilliamsonShmoys2011" class="citation cs2"><a href="David_P._Williamson" title="David P. Williamson">Williamson, David P.</a>; <a href="David_Shmoys" title="David Shmoys">Shmoys, David B.</a> (April 26, 2011), <i>The Design of Approximation Algorithms</i>, <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0521195270</bdi></cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li>Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, <a href="Marek_Karpinski" title="Marek Karpinski">Marek Karpinski</a> and <a href="Gerhard_J._Woeginger" title="Gerhard J. Woeginger">Gerhard Woeginger</a>, <a rel="nofollow" class="external text" href="https://www.csc.kth.se/tcs/compendium/"><i>A compendium of NP optimization problems</i></a>.</li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Optimization:_Algorithms,_methods,_and_heuristics381" style="padding:3px"><table class="nowraplinks hlist mw-collapsible expanded navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="3"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Optimization:_Algorithms,_methods,_and_heuristics381" style="font-size:114%;margin:0 4em"><a href="Mathematical_optimization" title="Mathematical optimization">Optimization</a>: <a href="Optimization_algorithm" class="mw-redirect" title="Optimization algorithm">Algorithms</a>, <a href="Iterative_method" title="Iterative method">methods</a>, and <a href="Heuristic_algorithm" class="mw-redirect" title="Heuristic algorithm">heuristics</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Unconstrained_nonlinear381" style="font-size:114%;margin:0 4em"><a href="Nonlinear_programming" title="Nonlinear programming">Unconstrained nonlinear</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Function_(mathematics)" title="Function (mathematics)">Functions</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Golden-section_search" title="Golden-section search">Golden-section search</a></li>

<li><a href="Powell's_method" title="Powell's method">Powell's method</a></li>

<li><a href="Line_search" title="Line search">Line search</a></li>

<li><a href="Nelder%E2%80%93Mead_method" title="Nelder–Mead method">Nelder–Mead method</a></li>

<li><a href="Successive_parabolic_interpolation" title="Successive parabolic interpolation">Successive parabolic interpolation</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Gradient" title="Gradient">Gradients</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Local_convergence" title="Local convergence">Convergence</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Trust_region" title="Trust region">Trust region</a></li>

<li><a href="Wolfe_conditions" title="Wolfe conditions">Wolfe conditions</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quasi-Newton_method" title="Quasi-Newton method">Quasi–Newton</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Berndt%E2%80%93Hall%E2%80%93Hall%E2%80%93Hausman_algorithm" title="Berndt–Hall–Hall–Hausman algorithm">Berndt–Hall–Hall–Hausman</a></li>

<li><a href="Broyden%E2%80%93Fletcher%E2%80%93Goldfarb%E2%80%93Shanno_algorithm" title="Broyden–Fletcher–Goldfarb–Shanno algorithm">Broyden–Fletcher–Goldfarb–Shanno</a> and <a href="Limited-memory_BFGS" title="Limited-memory BFGS">L-BFGS</a></li>

<li><a href="Davidon%E2%80%93Fletcher%E2%80%93Powell_formula" title="Davidon–Fletcher–Powell formula">Davidon–Fletcher–Powell</a></li>

<li><a href="Symmetric_rank-one" title="Symmetric rank-one">Symmetric rank-one (SR1)</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Iterative_method" title="Iterative method">Other methods</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Nonlinear_conjugate_gradient_method" title="Nonlinear conjugate gradient method">Conjugate gradient</a></li>

<li><a href="Gauss%E2%80%93Newton_algorithm" title="Gauss–Newton algorithm">Gauss–Newton</a></li>

<li><a href="Gradient_descent" title="Gradient descent">Gradient</a></li>

<li><a href="Mirror_descent" title="Mirror descent">Mirror</a></li>

<li><a href="Levenberg%E2%80%93Marquardt_algorithm" title="Levenberg–Marquardt algorithm">Levenberg–Marquardt</a></li>

<li><a href="Powell's_dog_leg_method" title="Powell's dog leg method">Powell's dog leg method</a></li>

<li><a href="Truncated_Newton_method" title="Truncated Newton method">Truncated Newton</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Hessian_matrix" title="Hessian matrix">Hessians</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Newton's_method_in_optimization" title="Newton's method in optimization">Newton's method</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td><td class="noviewer navbox-image" rowspan="5" style="width:1px;padding:0 0 0 2px"><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Constrained_nonlinear381" style="font-size:114%;margin:0 4em"><a href="Nonlinear_programming" title="Nonlinear programming">Constrained nonlinear</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Barrier_function" title="Barrier function">Barrier methods</a></li>

<li><a href="Penalty_method" title="Penalty method">Penalty methods</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Differentiable</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Augmented_Lagrangian_method" title="Augmented Lagrangian method">Augmented Lagrangian methods</a></li>

<li><a href="Sequential_quadratic_programming" title="Sequential quadratic programming">Sequential quadratic programming</a></li>

<li><a href="Successive_linear_programming" title="Successive linear programming">Successive linear programming</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Convex_optimization381" style="font-size:114%;margin:0 4em"><a href="Convex_optimization" title="Convex optimization">Convex optimization</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Convex_minimization" class="mw-redirect" title="Convex minimization">Convex<br> minimization</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Cutting-plane_method" title="Cutting-plane method">Cutting-plane method</a></li>

<li><a href="Frank%E2%80%93Wolfe_algorithm" title="Frank–Wolfe algorithm">Reduced gradient (Frank–Wolfe)</a></li>

<li><a href="Subgradient_method" title="Subgradient method">Subgradient method</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Linear_programming" title="Linear programming">Linear</a> and<br><a href="Quadratic_programming" title="Quadratic programming">quadratic</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Linear_programming#Interior_point" title="Linear programming">Interior point</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Affine_scaling" title="Affine scaling">Affine scaling</a></li>

<li><a href="Ellipsoid_method" title="Ellipsoid method">Ellipsoid algorithm of Khachiyan</a></li>

<li><a href="Karmarkar's_algorithm" title="Karmarkar's algorithm">Projective algorithm of Karmarkar</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Matroid" title="Matroid">Basis-</a><a href="Exchange_algorithm" class="mw-redirect" title="Exchange algorithm">exchange</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Simplex_algorithm" title="Simplex algorithm">Simplex algorithm of Dantzig</a></li>

<li><a href="Revised_simplex_method" title="Revised simplex method">Revised simplex algorithm</a></li>

<li><a href="Criss-cross_algorithm" title="Criss-cross algorithm">Criss-cross algorithm</a></li>

<li><a href="Lemke's_algorithm" title="Lemke's algorithm">Principal pivoting algorithm of Lemke</a></li>

<li><a href="Active-set_method" title="Active-set method">Active-set method</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible uncollapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Combinatorial381" style="font-size:114%;margin:0 4em"><a href="Combinatorial_optimization" title="Combinatorial optimization">Combinatorial</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">Paradigms</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul>

<li><a href="Dynamic_programming" title="Dynamic programming">Dynamic programming</a></li>

<li><a href="Greedy_algorithm" title="Greedy algorithm">Greedy algorithm</a></li>

<li><a href="Integer_programming" title="Integer programming">Integer programming</a>

<ul><li><a href="Branch_and_bound" title="Branch and bound">Branch and bound</a>/<a href="Branch_and_cut" title="Branch and cut">cut</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Graph_algorithm" class="mw-redirect" title="Graph algorithm">Graph<br> algorithms</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Minimum_spanning_tree52" scope="row" class="navbox-group" style="width:1%"><a href="Minimum_spanning_tree" title="Minimum spanning tree">Minimum<br> spanning tree</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bor%C5%AFvka's_algorithm" title="Borůvka's algorithm">Borůvka</a></li>

<li><a href="Kruskal's_algorithm" title="Kruskal's algorithm">Kruskal</a></li></ul>

</div></td></tr></tbody></table><div>

</div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Shortest_path39" scope="row" class="navbox-group" style="width:1%"><a href="Shortest_path_problem" title="Shortest path problem">Shortest path</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bellman%E2%80%93Ford_algorithm" title="Bellman–Ford algorithm">Bellman–Ford</a>

<li><a href="Dijkstra's_algorithm" title="Dijkstra's algorithm">Dijkstra</a></li>

<li><a href="Floyd%E2%80%93Warshall_algorithm" title="Floyd–Warshall algorithm">Floyd–Warshall</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Flow_network" title="Flow network">Network flows</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Dinic's_algorithm" title="Dinic's algorithm">Dinic</a></li>

<li><a href="Edmonds%E2%80%93Karp_algorithm" title="Edmonds–Karp algorithm">Edmonds–Karp</a></li>

<li><a href="Ford%E2%80%93Fulkerson_algorithm" title="Ford–Fulkerson algorithm">Ford–Fulkerson</a></li>

<li><a href="Push%E2%80%93relabel_maximum_flow_algorithm" title="Push–relabel maximum flow algorithm">Push–relabel maximum flow</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Metaheuristics381" style="font-size:114%;margin:0 4em"><a href="Metaheuristic" title="Metaheuristic">Metaheuristics</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Evolutionary_algorithm" title="Evolutionary algorithm">Evolutionary algorithm</a></li>

<li><a href="Hill_climbing" title="Hill climbing">Hill climbing</a></li>

<li><a href="Local_search_(optimization)" title="Local search (optimization)">Local search</a></li>

<li><a href="Parallel_metaheuristic" title="Parallel metaheuristic">Parallel metaheuristics</a></li>

<li><a href="Simulated_annealing" title="Simulated annealing">Simulated annealing</a></li>

<li><a href="Spiral_optimization_algorithm" title="Spiral optimization algorithm">Spiral optimization algorithm</a></li>

<li><a href="Tabu_search" title="Tabu search">Tabu search</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><td class="navbox-abovebelow" colspan="3"><div>

<ul><li><a href="Comparison_of_optimization_software" title="Comparison of optimization software">Software</a></li></ul>

</div></td></tr></tbody></table></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .tooltip-dotted{border-bottom:1px dotted;cursor:help}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox authority-control" aria-labelledby="Authority_control_databases_frameless&#124;text-top&#124;10px&#124;alt=Edit_this_at_Wikidata&#124;link=https&#58;//www.wikidata.org/wiki/Q621751#identifiers&#124;class=noprint&#124;Edit_this_at_Wikidata1345" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Authority_control_databases_frameless&#124;text-top&#124;10px&#124;alt=Edit_this_at_Wikidata&#124;link=https&#58;//www.wikidata.org/wiki/Q621751#identifiers&#124;class=noprint&#124;Edit_this_at_Wikidata1345" style="font-size:114%;margin:0 4em">Authority control databases </div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">National</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><a rel="nofollow" class="external text" href="https://d-nb.info/gnd/4500954-5">Germany</a></span></li><li><span class="uid"><span class="rt-commentedText tooltip tooltip-dotted" title="Approximation algorithms"><a rel="nofollow" class="external text" href="https://id.loc.gov/authorities/sh2009010988">United States</a></span></span></li><li><span class="uid"><span class="rt-commentedText tooltip tooltip-dotted" title="Algorithmes d'approximation"><a rel="nofollow" class="external text" href="https://catalogue.bnf.fr/ark:/12148/cb16603384f">France</a></span></span></li><li><span class="uid"><span class="rt-commentedText tooltip tooltip-dotted" title="Algorithmes d'approximation"><a rel="nofollow" class="external text" href="https://data.bnf.fr/ark:/12148/cb16603384f">BnF data</a></span></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://www.nli.org.il/en/authorities/987007475469205171">Israel</a></span></li></ul></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><a rel="nofollow" class="external text" href="https://lux.collections.yale.edu/view/concept/fdc2ae0c-bf65-44a9-925f-fc05addbfadf">Yale LUX</a></span></li></ul></div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-04-25" href="https://en.wikipedia.org/wiki/?title=Approximation_algorithm&oldid=1287316159">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>